local function sieve(N)
  local is_prime = {}
  is_prime[1] = false
  for n=2,N do
    is_prime[n] = true
  end
  local nprimes = 0
  for n=2,N do
    if is_prime[n] then
      nprimes = nprimes + 1
      for m=n+n,N,n do
        is_prime[m] = false
      end
    end
  end
  return nprimes
end

local res = sieve(10000000)
print(res)
assert(res == 664579)
